package com.sheng.leetcode.year2023.month09.day19;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2023/9/19
 * <p>
 * 2560. 打家劫舍 IV<p>
 * <p>
 * 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。<p>
 * 由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。<p>
 * 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。<p>
 * 给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。<p>
 * 另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。<p>
 * 返回小偷的 最小 窃取能力。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [2,3,5,9], k = 2<p>
 * 输出：5<p>
 * 解释：<p>
 * 小偷窃取至少 2 间房屋，共有 3 种方式：<p>
 * - 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。<p>
 * - 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。<p>
 * - 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。<p>
 * 因此，返回 min(5, 9, 9) = 5 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [2,7,9,3,1], k = 2<p>
 * 输出：2<p>
 * 解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^9<p>
 * 1 <= k <= (nums.length + 1)/2<p>
 */
public class LeetCode2560 {

    @Test
    public void test01() {
        int k = 2;
//        int[] nums = {2, 3, 5, 9};
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println(new Solution().minCapability(nums, k));
    }
}

class Solution {
    public int minCapability(int[] nums, int k) {
        // 从数组中选取非连续的 k 个元素 m 数组，获取这 m 中偷取金额最大值的最小情况
        // 即最小化 max(m)
        // 使用二分查找，试出最小的窃取能力
        int max = Arrays.stream(nums).max().orElse(Integer.MAX_VALUE);
        int min = 0;
        while (min < max) {
            int mid = (max + min) / 2;
            int count = maxStealCount(nums, mid);
            if (count < k) {
                // 能窃取 k
                min = mid + 1;
            } else {
                // 不能窃取 k
                max = mid;
            }
        }
        return min;
    }

    private int maxStealCount(int[] nums, int target) {
        // 数组中小于二分查找中位数的元素的数量，即可以窃取的房屋的数量
        int count = 0;
        // 循环数组 nums
        for (int i = 0; i < nums.length; i++) {
            // 数组元素小于等于二分查找中位数时
            if (nums[i] <= target) {
                // 窃取数量自增
                count++;
                // 跳过下一间房屋
                i++;
            }
        }
        return count;
    }
}
